<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.1.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/oldimgs/32.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/oldimgs/16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=sans-serif:300,300italic,400,400italic,700,700italic|Ubuntu:300,300italic,400,400italic,700,700italic|Roboto:300,300italic,400,400italic,700,700italic|'Open+Sans':300,300italic,400,400italic,700,700italic|'Microsoft+YaHei':300,300italic,400,400italic,700,700italic|sans-serif;:300,300italic,400,400italic,700,700italic|Source+Code+Pro:300,300italic,400,400italic,700,700italic|monospace:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14.0/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/pace-js@1.0.2/themes/blue/pace-theme-minimal.css">
  <script src="//cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"http:/ShuYuMo2003.github.io","root":"/","scheme":"Mist","version":"8.0.0","exturl":false,"sidebar":{"position":"left","width":230,"display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>

  <meta name="description" content="10.1学习总结目录 Day$1$-搜索 Day$2$-数据结构 Day$3$-图论 Day$4$-动态规划 Day$5$-数论 Day$6$-基础算法  Day1 搜索小目录 BFS DFS 枚举 二进制枚举">
<meta property="og:type" content="article">
<meta property="og:title" content="「学习总结」清北学堂 19 国庆">
<meta property="og:url" content="2019/%E3%80%90QBXT-20191001-20191007%E3%80%91MainNotice/index.html">
<meta property="og:site_name" content="Shu Yu Mo&#39;s blog">
<meta property="og:description" content="10.1学习总结目录 Day$1$-搜索 Day$2$-数据结构 Day$3$-图论 Day$4$-动态规划 Day$5$-数论 Day$6$-基础算法  Day1 搜索小目录 BFS DFS 枚举 二进制枚举">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike150%2C5%2C5%2C150%2C50/sign=7104e00d3dadcbef15397654cdc645b8/3b292df5e0fe99251d97b09938a85edf8cb17164.jpg">
<meta property="og:image" content="2019/【QBXT-20191001-20191007】MainNotice/4.png">
<meta property="og:image" content="2019/【QBXT-20191001-20191007】MainNotice/5.jpg">
<meta property="og:image" content="2019/【QBXT-20191001-20191007】MainNotice/6.png">
<meta property="og:image" content="2019/【QBXT-20191001-20191007】MainNotice/10.png">
<meta property="og:image" content="2019/【QBXT-20191001-20191007】MainNotice/9.png">
<meta property="article:published_time" content="2019-10-07T15:20:15.000Z">
<meta property="article:modified_time" content="2020-12-02T10:46:28.857Z">
<meta property="article:author" content="舒雨墨">
<meta property="article:tag" content="Shu Yu Mo&#39;s blog">
<meta property="article:tag" content="Blog">
<meta property="article:tag" content="OI">
<meta property="article:tag" content="Dr_OldSu">
<meta property="article:tag" content="舒阳">
<meta property="article:tag" content="life">
<meta property="article:tag" content="生活">
<meta property="article:tag" content="信息竞赛">
<meta property="article:tag" content="Shu_Yu_Mo">
<meta property="article:tag" content="ShuYuMo">
<meta property="article:tag" content="东营市第一中学">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike150%2C5%2C5%2C150%2C50/sign=7104e00d3dadcbef15397654cdc645b8/3b292df5e0fe99251d97b09938a85edf8cb17164.jpg">


<link rel="canonical" href="2019/【QBXT-20191001-20191007】MainNotice/">


<script data-pjax class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>「学习总结」清北学堂 19 国庆 | Shu Yu Mo's blog</title>
  






  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Shu Yu Mo's blog</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">远行者</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/link/" rel="section"><i class="fa fa-th fa-fw"></i>links</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-templates">

    <a href="/port/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>Templates</a>

  </li>
        <li class="menu-item menu-item-latex">

    <a href="/LaTeX-syntax.html" rel="section"><i class="fa fa-heartbeat fa-fw"></i>LaTeX</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav" style="display:none;">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <section class="post-toc-wrap sidebar-panel">

        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



        <hr/>
          <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#10-1%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93"><span class="nav-number">1.</span> <span class="nav-text">10.1学习总结</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%E7%9B%AE%E5%BD%95"><span class="nav-number">2.</span> <span class="nav-text">目录</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Day1-%E6%90%9C%E7%B4%A2"><span class="nav-number">3.</span> <span class="nav-text">Day1 搜索</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B0%8F%E7%9B%AE%E5%BD%95"><span class="nav-number">3.1.</span> <span class="nav-text">小目录</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%90%9C%E7%B4%A2"><span class="nav-number">3.2.</span> <span class="nav-text">搜索</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%90%9C%E7%B4%A2%E4%BC%98%E5%8C%96%C2%B7%E5%89%AA%E6%9E%9D"><span class="nav-number">3.3.</span> <span class="nav-text">搜索优化·剪枝</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#DBFS"><span class="nav-number">3.4.</span> <span class="nav-text">DBFS</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9E%9A%E4%B8%BE"><span class="nav-number">3.5.</span> <span class="nav-text">枚举</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E8%BF%9B%E5%88%B6%E6%9E%9A%E4%B8%BE%E5%AD%90%E9%9B%86"><span class="nav-number">3.6.</span> <span class="nav-text">二进制枚举子集</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#TODO-list"><span class="nav-number">3.7.</span> <span class="nav-text">TODO list</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%A2%98%E7%9B%AE"><span class="nav-number">3.8.</span> <span class="nav-text">题目</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Day2-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="nav-number">4.</span> <span class="nav-text">Day2 数据结构</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%9B%AE%E5%BD%95-1"><span class="nav-number">4.1.</span> <span class="nav-text">目录</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84"><span class="nav-number">4.2.</span> <span class="nav-text">树状数组</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%8A%9F%E8%83%BD%E6%89%A9%E5%B1%95"><span class="nav-number">4.2.1.</span> <span class="nav-text">功能扩展</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%90%AF%E5%8F%91%E5%BC%8F%E5%90%88%E5%B9%B6"><span class="nav-number">4.3.</span> <span class="nav-text">启发式合并</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A0%91%E4%B8%8A%E5%B7%AE%E5%88%86"><span class="nav-number">4.4.</span> <span class="nav-text">树上差分</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#DFS%E5%BA%8F%E5%88%97"><span class="nav-number">4.5.</span> <span class="nav-text">DFS序列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BA%BF%E6%AE%B5%E6%A0%91"><span class="nav-number">4.6.</span> <span class="nav-text">线段树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%BE%85%E5%AD%A6"><span class="nav-number">4.6.1.</span> <span class="nav-text">待学</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="nav-number">4.7.</span> <span class="nav-text">并查集</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%BE%85%E5%AD%A6-1"><span class="nav-number">4.7.1.</span> <span class="nav-text">待学</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#KMP"><span class="nav-number">4.8.</span> <span class="nav-text">KMP</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#bitset"><span class="nav-number">4.9.</span> <span class="nav-text">bitset</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%8F%AF%E5%B9%B6%E5%A0%86-%E5%B7%A6%E5%81%8F%E6%A0%91"><span class="nav-number">4.10.</span> <span class="nav-text">可并堆(左偏树)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%99%9A%E6%95%B0"><span class="nav-number">4.11.</span> <span class="nav-text">虚数</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Day3-%E5%9B%BE%E8%AE%BA"><span class="nav-number">5.</span> <span class="nav-text">Day3 图论</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#2-SAT"><span class="nav-number">5.1.</span> <span class="nav-text">2-SAT</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#SomeThing"><span class="nav-number">5.1.1.</span> <span class="nav-text">SomeThing</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%8A%A0%E8%BE%B9%E8%A7%84%E5%88%99"><span class="nav-number">5.1.2.</span> <span class="nav-text">加边规则</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E9%A2%98"><span class="nav-number">5.1.3.</span> <span class="nav-text">例题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BA%8C%E5%88%86%E5%9B%BE"><span class="nav-number">5.2.</span> <span class="nav-text">二分图</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#SomeThing-1"><span class="nav-number">5.2.1.</span> <span class="nav-text">SomeThing</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E9%A2%98-1"><span class="nav-number">5.2.2.</span> <span class="nav-text">例题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9C%80%E5%A4%A7%E5%9B%A2"><span class="nav-number">5.3.</span> <span class="nav-text">最大团</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#SomeThing-2"><span class="nav-number">5.3.1.</span> <span class="nav-text">SomeThing</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E9%A2%98-2"><span class="nav-number">5.3.2.</span> <span class="nav-text">例题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9C%80%E5%A4%A7%E7%8B%AC%E7%AB%8B%E9%9B%86"><span class="nav-number">5.4.</span> <span class="nav-text">最大独立集</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Day4-DPDPDPDPDP-amp-amp-%E8%AE%B2%E9%A2%98"><span class="nav-number">6.</span> <span class="nav-text">Day4 DPDPDPDPDP &amp;&amp; 讲题</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%9B%BE%E8%AE%BA%E6%8A%80%E5%B7%A7"><span class="nav-number">6.1.</span> <span class="nav-text">图论技巧</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#K-DP-3%E7%BB%B4%E6%8C%87%E9%92%88"><span class="nav-number">6.2.</span> <span class="nav-text">***K DP(3维指针)</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%8C%BA%E9%97%B4DP"><span class="nav-number">6.3.</span> <span class="nav-text">区间DP</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%8E%92%E5%88%97DP"><span class="nav-number">6.4.</span> <span class="nav-text">排列DP</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#DP-%E4%BC%98%E5%8C%96"><span class="nav-number">6.5.</span> <span class="nav-text">DP 优化</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BE%8B%E9%A2%98-3"><span class="nav-number">6.6.</span> <span class="nav-text">例题</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97%E8%AE%A1%E6%95%B0"><span class="nav-number">6.6.1.</span> <span class="nav-text">回文子序列计数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%BB%99%E5%87%BA%E4%B8%80%E4%B8%AA%E6%97%A0%E9%99%90%E5%A4%A7%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91%E9%97%AE%E9%80%89n%E4%B8%AA%E7%82%B9%EF%BC%8C%E4%B8%80%E7%9B%B4%E9%80%89%E5%88%B0k%E5%B1%82%EF%BC%8C%E6%80%BB%E5%85%B1%E7%9A%84%E6%96%B9%E6%A1%88%E6%95%B0"><span class="nav-number">6.6.2.</span> <span class="nav-text">给出一个无限大的二叉树问选n个点，一直选到k层，总共的方案数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%BB%99%E5%87%BAn%E4%B8%AA%E6%95%B0%EF%BC%8C%E5%9C%A8m%E7%9A%84%E8%8C%83%E5%9B%B4%E5%86%85%EF%BC%8C%E6%AF%8F%E4%B8%AA%E6%95%B0%E5%AD%97%E5%8F%AF%E6%9E%84%E6%88%90-i-i-i-%E5%92%8C-i-1-i-i-1-%E4%B8%89%E5%85%83%E7%BB%84%EF%BC%8C%E6%AF%8F%E4%B8%AA%E6%95%B0%E5%AD%97%E5%8F%AA%E8%83%BD%E7%94%A8%E4%BA%8E%E6%9E%84%E6%88%90%E4%B8%80%E4%B8%AA%E4%B8%89%E5%85%83%E7%BB%84%EF%BC%8C%E6%9C%80%E5%A4%A7%E5%8C%96%E4%B8%89%E5%85%83%E7%BB%84%E7%BB%84%E6%88%90%E7%9A%84%E6%95%B0%E9%87%8F"><span class="nav-number">6.6.3.</span> <span class="nav-text">给出n个数，在m的范围内，每个数字可构成[i, i, i]和[i - 1, i , i + 1]三元组，每个数字只能用于构成一个三元组，最大化三元组组成的数量</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%BB%99%E5%87%BA%E9%95%BF%E5%BA%A6%E4%B8%BAn%E7%9A%84%E5%BA%8F%E5%88%97-Q%E6%AC%A1%E6%93%8D%E4%BD%9C-%E6%AF%8F%E6%AC%A1%E6%93%8D%E4%BD%9C%E4%BA%A4%E6%8D%A2%E6%88%96%E8%80%85%E4%B8%8D%E4%BA%A4%E6%8D%A2%E4%B8%A4%E4%B8%AA%E6%95%B0-%E5%9C%A8-2-Q-%E7%A7%8D%E6%96%B9%E6%A1%88%E4%B8%AD%EF%BC%8C%E9%80%86%E5%BA%8F%E5%AF%B9%E6%95%B0%E9%87%8F%E6%80%BB%E5%92%8C%E3%80%82"><span class="nav-number">6.6.4.</span> <span class="nav-text">给出长度为n的序列 Q次操作 每次操作交换或者不交换两个数 在$2^Q$种方案中，逆序对数量总和。</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9C%9F%E6%9C%9B"><span class="nav-number">6.7.</span> <span class="nav-text">期望</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Day5%E6%95%B0%E8%AE%BA"><span class="nav-number">7.</span> <span class="nav-text">Day5数论</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E5%89%B2%E5%BA%8F%E5%88%97"><span class="nav-number">7.1.</span> <span class="nav-text">分割序列</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E3%80%90%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0%E3%80%91"><span class="nav-number">7.1.1.</span> <span class="nav-text">【题目描述】</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%8A%B6%E6%80%81"><span class="nav-number">7.1.2.</span> <span class="nav-text">状态</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E8%BD%AC%E7%A7%BB%E6%96%B9%E7%A8%8B"><span class="nav-number">7.1.3.</span> <span class="nav-text">转移方程</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BC%98%E5%8C%96"><span class="nav-number">7.1.4.</span> <span class="nav-text">优化</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%9F%A9%E9%98%B5"><span class="nav-number">7.2.</span> <span class="nav-text">矩阵</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%B8%80%E9%81%93%E4%BE%8B%E9%A2%98"><span class="nav-number">7.2.1.</span> <span class="nav-text">一道例题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#exGCD"><span class="nav-number">7.3.</span> <span class="nav-text">exGCD</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%AD%9B%E6%B3%95"><span class="nav-number">7.4.</span> <span class="nav-text">筛法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E7%B4%A0%E6%95%B0%E7%AD%9B"><span class="nav-number">7.4.1.</span> <span class="nav-text">素数筛</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0"><span class="nav-number">7.5.</span> <span class="nav-text">欧拉函数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#GCD"><span class="nav-number">7.6.</span> <span class="nav-text">GCD</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86-amp-amp-%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86"><span class="nav-number">7.7.</span> <span class="nav-text">费马小定理 &amp;&amp; 欧拉定理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E9%80%86%E5%85%83"><span class="nav-number">7.8.</span> <span class="nav-text">逆元</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E7%BB%84%E5%90%88%E6%95%B0"><span class="nav-number">7.9.</span> <span class="nav-text">组合数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Lucas%E5%AE%9A%E7%90%86"><span class="nav-number">7.10.</span> <span class="nav-text">Lucas定理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86CRT"><span class="nav-number">7.11.</span> <span class="nav-text">中国剩余定理CRT</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Guass%E6%B6%88%E5%85%83"><span class="nav-number">7.12.</span> <span class="nav-text">Guass消元</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A4%A7%E6%AD%A5%E5%B0%8F%E6%AD%A5%E5%AE%9A%E7%90%86-BSGS"><span class="nav-number">7.13.</span> <span class="nav-text">大步小步定理(BSGS)</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Day6-%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95"><span class="nav-number">8.</span> <span class="nav-text">Day6 基础算法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#Day6-T2"><span class="nav-number">8.1.</span> <span class="nav-text">Day6 T2</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A8%A1%E6%8B%9F"><span class="nav-number">8.2.</span> <span class="nav-text">模拟</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E9%A2%98-4"><span class="nav-number">8.2.1.</span> <span class="nav-text">例题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%B4%AA%E5%BF%83"><span class="nav-number">8.3.</span> <span class="nav-text">贪心</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%88%86%E6%B2%BB"><span class="nav-number">8.4.</span> <span class="nav-text">分治</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#Last-Day"><span class="nav-number">9.</span> <span class="nav-text">Last Day</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#CSP-Algorithm"><span class="nav-number">10.</span> <span class="nav-text">CSP-Algorithm</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%95%B0%E8%AE%BA"><span class="nav-number">10.1.</span> <span class="nav-text">数论</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%9B%BE%E8%AE%BA"><span class="nav-number">10.2.</span> <span class="nav-text">图论</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%A8%A1%E6%8B%9F-1"><span class="nav-number">10.3.</span> <span class="nav-text">模拟</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#SomeThing-3"><span class="nav-number">10.4.</span> <span class="nav-text">SomeThing</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E8%80%83%E8%AF%95%E6%B3%A8%E6%84%8F"><span class="nav-number">10.5.</span> <span class="nav-text">考试注意</span></a></li></ol></li></ol></div>
      </section>
      <!--/noindex-->

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



      </section>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">
      

      

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2019/【QBXT-20191001-20191007】MainNotice/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          「学习总结」清北学堂 19 国庆
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2019-10-07 23:20:15" itemprop="dateCreated datePublished" datetime="2019-10-07T23:20:15+08:00">2019-10-07</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-12-02 18:46:28" itemprop="dateModified" datetime="2020-12-02T18:46:28+08:00">2020-12-02</time>
      </span>

  
    <span id="2019/【QBXT-20191001-20191007】MainNotice/" class="post-meta-item leancloud_visitors" data-flag-title="「学习总结」清北学堂 19 国庆" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2019/【QBXT-20191001-20191007】MainNotice/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2019/【QBXT-20191001-20191007】MainNotice/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>7.5k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>7 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h1 id="10-1学习总结"><a href="#10-1学习总结" class="headerlink" title="10.1学习总结"></a>10.1学习总结</h1><h1 id="目录"><a href="#目录" class="headerlink" title="目录"></a>目录</h1><ul>
<li><code>Day</code>$1$-<strong>搜索</strong></li>
<li><code>Day</code>$2$-<strong>数据结构</strong></li>
<li><code>Day</code>$3$-<strong>图论</strong></li>
<li><code>Day</code>$4$-<strong>动态规划</strong></li>
<li><code>Day</code>$5$-<strong>数论</strong></li>
<li><code>Day</code>$6$-<strong>基础算法</strong></li>
</ul>
<h1 id="Day1-搜索"><a href="#Day1-搜索" class="headerlink" title="Day1 搜索"></a>Day1 搜索</h1><h2 id="小目录"><a href="#小目录" class="headerlink" title="小目录"></a>小目录</h2><ul>
<li>BFS</li>
<li>DFS</li>
<li>枚举</li>
<li>二进制枚举</li>
</ul>
<a id="more"></a>

<h2 id="搜索"><a href="#搜索" class="headerlink" title="搜索"></a>搜索</h2><ul>
<li>最大独立集合问题<ul>
<li>反图就是最大团</li>
</ul>
</li>
</ul>
<h2 id="搜索优化·剪枝"><a href="#搜索优化·剪枝" class="headerlink" title="搜索优化·剪枝"></a>搜索优化·剪枝</h2><ul>
<li>如果一个点无法加入当前子图，那么该点在之后也无法被加入当前子图</li>
<li>除了状态以外，最坏的复杂度应该是在枚举可选的点<br>如何减少枚举？<pre><code> 记录一个可扩展序列，每次从可扩展序列中选择点进行扩展
 每次往后扩展一个点，即用当前点更新可扩展序列
 由性质知，下一层的可扩展序列只可能是当前可扩展序列的一个子序列</code></pre>
</li>
<li>考虑可扩展序列中剩下的点数能否达成目标</li>
<li>考虑从i号点往后扩展的最大答案能否达成目标<br>由于需要求从i号点往后扩展的最大答案，因此可以倒着求每个点往后扩展的最大答案<br>容易知道，当前位置的最大答案最多只能是上一个位置加一，即𝑀𝑎𝑥[𝑖]≤𝑀𝑎x[𝑖+1+1</li>
</ul>
<h2 id="DBFS"><a href="#DBFS" class="headerlink" title="DBFS"></a>DBFS</h2><ul>
<li>双向BFS</li>
<li>初始队列加入起点和终点</li>
<li>当出现交点，就得出答案</li>
</ul>
<h2 id="枚举"><a href="#枚举" class="headerlink" title="枚举"></a>枚举</h2><ul>
<li>枚举：基于已知信息的猜测,从可能的答案集合中枚举并验证<br>验证复杂度尽可能小<br>枚举范围尽可能小（利用条件缩小枚举空间）<br>选择合理的枚举顺序（正序，倒序）</li>
<li>枚举什么？<br>怎么枚举？<br>怎么减少枚举？</li>
</ul>
<h2 id="二进制枚举子集"><a href="#二进制枚举子集" class="headerlink" title="二进制枚举子集"></a>二进制枚举子集</h2><ul>
<li><code>for(int S1=S;S1!=0;S1=(S1-1)&amp;S)&#123;</code></li>
</ul>
<h2 id="TODO-list"><a href="#TODO-list" class="headerlink" title="TODO list"></a>TODO list</h2><ul>
<li>最大团、最大独立集求法</li>
<li>双向BFS具体</li>
</ul>
<h2 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h2><ul>
<li>洪水</li>
<li>辛苦的老园丁</li>
<li>生日蛋糕</li>
<li>靶形数独</li>
<li>棋盘分割</li>
<li>密室逃脱</li>
<li>Prime Path[ 1s 64M ] </li>
<li>拯救行动</li>
<li>苹果消消乐【1s 64MB】</li>
<li>Matrix  [ 2s  512MB ]  –一个矩形的价值定义为矩形4个顶点上的元素价值的最小值</li>
<li>特殊密码锁</li>
<li>恼人的青蛙[2s]</li>
<li>熄灯问题【1s 64MB】</li>
</ul>
<h1 id="Day2-数据结构"><a href="#Day2-数据结构" class="headerlink" title="Day2 数据结构"></a>Day2 数据结构</h1><h2 id="目录-1"><a href="#目录-1" class="headerlink" title="目录"></a>目录</h2><ul>
<li>树状数组</li>
<li>树上倍增</li>
<li>启发式合并</li>
<li>树上差分</li>
<li>DFS序列</li>
<li>线段树</li>
<li>并查集</li>
</ul>
<h2 id="树状数组"><a href="#树状数组" class="headerlink" title="树状数组"></a>树状数组</h2><ul>
<li>扩展困难</li>
<li>局限性大</li>
<li>代码量小</li>
<li>常数因子小</li>
<li>单点修改，区间查询</li>
<li>操作$O(log n)$</li>
<li>信息可加性<h3 id="功能扩展"><a href="#功能扩展" class="headerlink" title="功能扩展"></a>功能扩展</h3></li>
<li>区间修改，区间查询<ul>
<li>思路：<ul>
<li>朴素区间修改方式：维护差分数组$d_i = a_i - a_{i - 1}$</li>
<li>$a_x = \sum d_i$</li>
<li>维护区间差分 </li>
</ul>
</li>
<li>课件第9页</li>
</ul>
</li>
</ul>
<h2 id="启发式合并"><a href="#启发式合并" class="headerlink" title="启发式合并"></a>启发式合并</h2><ul>
<li>小集合插入大的集合</li>
<li>均摊复杂度小</li>
</ul>
<h2 id="树上差分"><a href="#树上差分" class="headerlink" title="树上差分"></a>树上差分</h2><ul>
<li>( <code>u</code> —-&gt; <code>v</code> )  ===&gt;  +u到root的路径 + v到root的路径 - lca（u, v)到root的路径</li>
<li>某个节点的数值表示，根到当前点的区间增加量</li>
</ul>
<h2 id="DFS序列"><a href="#DFS序列" class="headerlink" title="DFS序列"></a>DFS序列</h2><ul>
<li>记录每个节点再DFS中进出栈的时间序列</li>
<li>将树形结构线性化</li>
<li>任意子树的DFS序列都是连续的</li>
<li>两点之间的路径就是<code>DFS</code>序列中两点之间出现次数为1的结点+LCA()</li>
<li>树链修改 + 子树和查询<ul>
<li>我们假设 $u$ 的子树中一节点 $v$ 到根节点路径的总修改量为 $w[v]$，则 $v$ 对 $u$ 的子树和贡献为 $w[v]<em>(dep[v]-dep[u]+1)=w[v]</em>(dep[v]+1)-w[v]*dep[u]$ </li>
<li>故以 $u$ 为根的子树的总贡献为 $\sum w[v]*(dep[v]+1)-dep[u]*Σw[v]$ </li>
<li>所以只需要用两个数据结构，一个维护 $w[v]$ 的单点修改与区间求和， 另一个维护 $w[v]*(dep[v]+1)$ 的单点修改与区间求和即可</li>
</ul>
</li>
<li>单点修改 + 树链和查询<ul>
<li>考虑一个点 u 修改后对 v 到根节点的权值有影响当且仅当 u 为 v 的祖 先, 所以每次修改相当于子树修改, 单点查询, 再利用 dfs 变为区间修 改，单点查询</li>
</ul>
</li>
</ul>
<h2 id="线段树"><a href="#线段树" class="headerlink" title="线段树"></a>线段树</h2><ul>
<li>需要考虑的问题<ul>
<li>标记下放需要需要信息与标记的合并，标记与标记的合并 </li>
<li>合并子树信息需要信息与信息的合并</li>
<li>需要存储的信息<h3 id="待学"><a href="#待学" class="headerlink" title="待学"></a>待学</h3></li>
</ul>
</li>
<li>线段树启发式合并</li>
<li>线段树可持久化</li>
<li>主席树</li>
</ul>
<h2 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a>并查集</h2><ul>
<li>可持久化方式：可持久化线段树维护$fa$数组</li>
<li>种类并查集<ul>
<li>特征性质并查集</li>
</ul>
</li>
<li>插销最后一步操作<ul>
<li>按秩合并，取消路径压缩优化</li>
</ul>
</li>
</ul>
<h3 id="待学-1"><a href="#待学-1" class="headerlink" title="待学"></a>待学</h3><ul>
<li>带权并查集<ul>
<li>满足可加性</li>
</ul>
</li>
</ul>
<h2 id="KMP"><a href="#KMP" class="headerlink" title="KMP"></a>KMP</h2><pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp">f<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span>_R <span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>i <span class="token operator">&lt;=</span> m<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> j <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>j <span class="token operator">&amp;&amp;</span> p<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> p<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> j <span class="token operator">=</span> f<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
    f<span class="token punctuation">[</span>i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> p<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> p<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">?</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">:</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

<h2 id="bitset"><a href="#bitset" class="headerlink" title="bitset"></a>bitset</h2><ul>
<li>BZOJ4713 迷失的字符串</li>
<li>由于dp所存储的down和up都是bool类型的变量，因此可以用bitset存储</li>
<li>对于所有j，up和down都是从j-1的位置转移过来的。<br>可以直接用bitset转移，复杂度O(N/32)</li>
<li>bitset也可以直接合并</li>
<li>总复杂度O(N^2/32)</li>
</ul>
<h2 id="可并堆-左偏树"><a href="#可并堆-左偏树" class="headerlink" title="可并堆(左偏树)"></a>可并堆(左偏树)</h2><blockquote>
<p>其实这个是涉及到两个堆合并的问题，那么就可以使用可并堆了<br>左偏树是一种可并堆</p>
</blockquote>
<blockquote>
<p>考虑刚才的启发式合并，其实它将堆的顺序打乱了，也就是它没有利用堆中原本的大小顺序<br>其实这个大小顺序是可以利用的<br>首先可以比较两个堆的根的大小顺序<br>考虑将另一个堆插入左儿子还是右儿子，其实不论插入哪边都是可以的<br>那么插入哪一边复杂度更小？</p>
</blockquote>
<blockquote>
<p>合并与层数有关<br>插入层数较小的一边复杂度更优<br>这样也能保证层数不会增加太多<br>每次合并复杂度为O(log(N))<br>总复杂度为O(N*log(N))</p>
</blockquote>
<h2 id="虚数"><a href="#虚数" class="headerlink" title="虚数"></a>虚数</h2><blockquote>
<p>将图中的一些节点提出，保留树的形态不变<br>用这些取出的关键点代表这棵树</p>
</blockquote>
<h1 id="Day3-图论"><a href="#Day3-图论" class="headerlink" title="Day3 图论"></a>Day3 图论</h1><h2 id="2-SAT"><a href="#2-SAT" class="headerlink" title="2-SAT"></a>2-SAT</h2><h3 id="SomeThing"><a href="#SomeThing" class="headerlink" title="SomeThing"></a>SomeThing</h3><ul>
<li>又名2-SAT-2</li>
<li>判断有无解</li>
<li>确定变量</li>
<li>确定关系表达式</li>
<li>变量的取值有两种</li>
<li>%d - SAT 表达式有多少个变量</li>
<li>SAT - %d 每个变量的情况个数<h3 id="加边规则"><a href="#加边规则" class="headerlink" title="加边规则"></a>加边规则</h3></li>
</ul>
<ol>
<li><p>$X_1 and X_2 = False$ 那么添加边</p>
<blockquote>
<p>$X1_{true} -&gt; X2_{false}$和$X2_{false} -&gt; X1_{true}$</p>
</blockquote>
</li>
<li><p>$X_1 and X_2 = True$ 那么添加边</p>
<blockquote>
<p>$X1_{false} -&gt; X1_{true}$ 和 $X2_{false} -&gt; X2_{true}$    </p>
</blockquote>
</li>
<li><p>$X_1 or X_2 = True$ 那么添加边</p>
<blockquote>
<p>$X1_{false} -&gt; X2_{true}$和$X2_{false} -&gt; X1_{true}$</p>
</blockquote>
</li>
<li><p>$X_1 or X_2 = false$ 那么添加边</p>
<blockquote>
<p>$X1_{true} -&gt; X1_{false}$和$X2_{true} -&gt; X2_{false}$</p>
</blockquote>
</li>
</ol>
<blockquote>
<p>如果$x –&gt; y$，表示确定<code>x</code>即可确定<code>y</code>。<br>(当某个点必须为某个值的时候，自身连边，例：当必须为true时，就false连向true)</p>
</blockquote>
<h3 id="例题"><a href="#例题" class="headerlink" title="例题"></a>例题</h3><ul>
<li>POJ2446</li>
<li>HDU3622</li>
<li>UVA1514 Piece it together</li>
<li>UVA1086 The Ministers’ Major Mess</li>
<li>HDU4306<h2 id="二分图"><a href="#二分图" class="headerlink" title="二分图"></a>二分图</h2><h3 id="SomeThing-1"><a href="#SomeThing-1" class="headerlink" title="SomeThing"></a>SomeThing</h3></li>
<li><code>此图是树</code> =&gt; <code>此图是二分图</code></li>
<li><code>此图是二分图</code> =&gt; <code>此图是树</code></li>
<li>二分图两边的点数量为$n$,$m$，匹配值是$x$<ul>
<li>一些奇奇怪怪的数量是$x$, $n - x$, $m - x$,$n + m - x$ ,$n + m - 2 \times x$</li>
<li>最大独立集数量为$n + m - x$</li>
</ul>
</li>
</ul>
<h3 id="例题-1"><a href="#例题-1" class="headerlink" title="例题"></a>例题</h3><ol>
<li><blockquote>
<ul>
<li>给出一张图，删一条边，使之成为二分图（CF 19E Fairy）</li>
</ul>
</blockquote>
<blockquote>
<p>删掉那些在奇圈的交集上的边</p>
</blockquote>
</li>
</ol>
<h2 id="最大团"><a href="#最大团" class="headerlink" title="最大团"></a>最大团</h2><h3 id="SomeThing-2"><a href="#SomeThing-2" class="headerlink" title="SomeThing"></a>SomeThing</h3><ul>
<li>给一张图，求最大团 —&gt; <code>NPC</code>。</li>
<li>所以很多问题中，求最大团的图有很多特殊性质。</li>
<li>求最大团的方法 （wait）。</li>
<li>补图 —&gt; <code>把图之前的图上的边全都删掉，没有的边全都加上</code>。</li>
<li>原图的反图中的最大独立集就是最大团<h3 id="例题-2"><a href="#例题-2" class="headerlink" title="例题"></a>例题</h3></li>
<li>【HEOI2012】朋友圈<h2 id="最大独立集"><a href="#最大独立集" class="headerlink" title="最大独立集"></a>最大独立集</h2></li>
<li>原图的反图就是最大团。</li>
<li>在二分图中，独立集的个数为，$n$和$m$是二分图中的$n + m - x$<br><img src="https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/c0%3Dbaike150%2C5%2C5%2C150%2C50/sign=7104e00d3dadcbef15397654cdc645b8/3b292df5e0fe99251d97b09938a85edf8cb17164.jpg" alt="independent"></li>
</ul>
<h1 id="Day4-DPDPDPDPDP-amp-amp-讲题"><a href="#Day4-DPDPDPDPDP-amp-amp-讲题" class="headerlink" title="Day4 DPDPDPDPDP &amp;&amp; 讲题"></a>Day4 DPDPDPDPDP &amp;&amp; 讲题</h1><h2 id="图论技巧"><a href="#图论技巧" class="headerlink" title="图论技巧"></a>图论技巧</h2><ul>
<li>线段树优化建图<ul>
<li><a target="_blank" rel="noopener" href="https://www.cnblogs.com/Miracevin/p/9863080.html">https://www.cnblogs.com/Miracevin/p/9863080.html</a> <h2 id="K-DP-3维指针"><a href="#K-DP-3维指针" class="headerlink" title="***K DP(3维指针)"></a>***K DP<del>(3维指针)</del></h2></li>
</ul>
</li>
<li>三种类型<ul>
<li>已知自己算出别人</li>
<li>已知别人算出自己</li>
<li>记忆化搜索<h2 id="区间DP"><a href="#区间DP" class="headerlink" title="区间DP"></a>区间DP</h2></li>
</ul>
</li>
<li><blockquote>
<p>两种 $f[i][j] = min/max/sum{f[i + 1][j], f[i][j - 1]}$<br>$f[i][j] = min/max/sum{f[i][k], f[k + 1[j]]}$</p>
</blockquote>
</li>
</ul>
<h2 id="排列DP"><a href="#排列DP" class="headerlink" title="排列DP"></a>排列DP</h2><ul>
<li>考虑把一个数从小到大或者从大到小以此插入</li>
<li>一个排列的前缀都是排列</li>
<li>现在$[1, k]$已经是一个$1 - k$的排列了，那么如果加一个数字$x$,如果这个数字$x$，$1 &lt;= x &lt;= k$，那么将所有$[1, k]$之间，大于等于数字x的数字$+ 1$即可<h2 id="DP-优化"><a href="#DP-优化" class="headerlink" title="DP 优化"></a>DP 优化</h2></li>
<li>根据的性质<ul>
<li>单调性</li>
<li>前缀和</li>
</ul>
</li>
<li>分析方程，思考决策点的位置<h2 id="例题-3"><a href="#例题-3" class="headerlink" title="例题"></a>例题</h2><h3 id="回文子序列计数"><a href="#回文子序列计数" class="headerlink" title="回文子序列计数"></a>回文子序列计数</h3></li>
</ul>
<h3 id="给出一个无限大的二叉树问选n个点，一直选到k层，总共的方案数"><a href="#给出一个无限大的二叉树问选n个点，一直选到k层，总共的方案数" class="headerlink" title="给出一个无限大的二叉树问选n个点，一直选到k层，总共的方案数"></a>给出一个无限大的二叉树问选n个点，一直选到k层，总共的方案数</h3><ul>
<li>设计状态f[i][j]为用了i个点，选到了j层<ul>
<li>发现无法转移状态</li>
<li>由于转移需要最后一层的选择情况，加一个状态</li>
</ul>
</li>
<li>设计状态f[i][j][k]为用了i个点，选到了j层，第j层有k个点被选<ul>
<li>转移困难</li>
<li>复杂度大</li>
<li>状态限制性过强</li>
</ul>
</li>
<li>设计状态f[i][j]为用了i个点，深度小于等于j的方案数<ul>
<li>考虑转移：<ul>
<li>拆根法，拆掉根节点，成为两个问题相同，规模更小的子问题，进行转移</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="给出n个数，在m的范围内，每个数字可构成-i-i-i-和-i-1-i-i-1-三元组，每个数字只能用于构成一个三元组，最大化三元组组成的数量"><a href="#给出n个数，在m的范围内，每个数字可构成-i-i-i-和-i-1-i-i-1-三元组，每个数字只能用于构成一个三元组，最大化三元组组成的数量" class="headerlink" title="给出n个数，在m的范围内，每个数字可构成[i, i, i]和[i - 1, i , i + 1]三元组，每个数字只能用于构成一个三元组，最大化三元组组成的数量"></a>给出n个数，在m的范围内，每个数字可构成[i, i, i]和[i - 1, i , i + 1]三元组，每个数字只能用于构成一个三元组，最大化三元组组成的数量</h3><ul>
<li>状态：$f[i][j][k]$ 用了j个i-1，i，i+1与k个i，i+1，i+2的方案，枚举l个i+1，i+2，i+3。</li>
<li><a target="_blank" rel="noopener" href="http://codeforces.com/problemset/problem/1110/D">http://codeforces.com/problemset/problem/1110/D</a></li>
</ul>
<h3 id="给出长度为n的序列-Q次操作-每次操作交换或者不交换两个数-在-2-Q-种方案中，逆序对数量总和。"><a href="#给出长度为n的序列-Q次操作-每次操作交换或者不交换两个数-在-2-Q-种方案中，逆序对数量总和。" class="headerlink" title="给出长度为n的序列 Q次操作 每次操作交换或者不交换两个数 在$2^Q$种方案中，逆序对数量总和。"></a>给出长度为n的序列 Q次操作 每次操作交换或者不交换两个数 在$2^Q$种方案中，逆序对数量总和。</h3><ul>
<li>AtCoder 030D</li>
</ul>
<h2 id="期望"><a href="#期望" class="headerlink" title="期望"></a>期望</h2><ul>
<li>某种意义下的加权平均值</li>
<li>期望的和等于和的期望</li>
</ul>
<h1 id="Day5数论"><a href="#Day5数论" class="headerlink" title="Day5数论"></a>Day5数论</h1><h2 id="分割序列"><a href="#分割序列" class="headerlink" title="分割序列"></a>分割序列</h2><h3 id="【题目描述】"><a href="#【题目描述】" class="headerlink" title="【题目描述】"></a>【题目描述】</h3><p>给定一个长度为$n$的序列 $v[1..n]$，现在要将这个序列分成$ k $段（每段都不能为空），定义每一段的权值为该段上的所有数的戒和。定义整个序列的权值为每段权值的和。问：这个<br>序列的最大权值为多少。</p>
<h3 id="状态"><a href="#状态" class="headerlink" title="状态"></a>状态</h3><ul>
<li>f[i][j] 在前i个数字中，分成j段的最大或和值。<h3 id="转移方程"><a href="#转移方程" class="headerlink" title="转移方程"></a>转移方程</h3></li>
<li><blockquote>
<p>$$f[i][j] = \max f[k][j - 1] + w[k][j]$$</p>
</blockquote>
<h3 id="优化"><a href="#优化" class="headerlink" title="优化"></a>优化</h3></li>
<li>利用单调性</li>
<li>WQS二分</li>
</ul>
<h2 id="矩阵"><a href="#矩阵" class="headerlink" title="矩阵"></a>矩阵</h2><ul>
<li>递推矩阵</li>
<li>不断重复某个操作</li>
<li>线性代数中的向量变幻</li>
<li>操作对应转移矩阵</li>
<li>具有结合律，无分配律</li>
<li><a target="_blank" rel="noopener" href="https://www.cnblogs.com/fengff/p/9758272.html">https://www.cnblogs.com/fengff/p/9758272.html</a><h3 id="一道例题"><a href="#一道例题" class="headerlink" title="一道例题"></a>一道例题</h3></li>
<li>构造一个大整数，给定一个N和M，将1..N依次接在这个整数的后面，求 1234567891011121314….N % M, <ul>
<li>M为int范围内且为质数</li>
<li>N &lt;= 1e18</li>
</ul>
</li>
<li>思路<ul>
<li>根据数据规模时间复杂度为$O(logn)$</li>
<li>F[t]表示将1..t拼成一个大整数模M的值</li>
<li>F[t] = F[t - 1] * 10^k + (t - 1) + 1<pre class="line-numbers language-none"><code class="language-none">- A     &#x3D; [ F[t - 1]   (t - 1)    1 ]

- A * D &#x3D; [ F[t]       (t)        1 ]

          | 10^k        0        0  | 
- D     &#x3D; |  1          1        0  |            
          |  1          1        1  |     <span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="exGCD"><a href="#exGCD" class="headerlink" title="exGCD"></a>exGCD</h2></li>
</ul>
</li>
<li>裴蜀定理，判断是否有解</li>
<li>求出$ax + by = gcd(a, b)$的一条个整数解</li>
<li>QAQ<ul>
<li>列出同余方程</li>
<li>转成不定方程</li>
<li>整理，转换成欧几里得方程一般形式</li>
<li>exGCD求解</li>
</ul>
</li>
</ul>
<h2 id="筛法"><a href="#筛法" class="headerlink" title="筛法"></a>筛法</h2><h3 id="素数筛"><a href="#素数筛" class="headerlink" title="素数筛"></a>素数筛</h3><ul>
<li><p>埃拉托尼斯筛法</p>
<ul>
<li>$O(n log log n)$</li>
</ul>
</li>
<li><p>欧拉筛法</p>
<ul>
<li>$O(n)$</li>
<li>每个数都只会且仅只会被最小质因子筛去</li>
<li><pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token keyword">for</span> i in each_Num<span class="token operator">:</span>
    <span class="token keyword">for</span> j in each_Prime<span class="token operator">:</span>
        vis<span class="token punctuation">[</span>i <span class="token operator">*</span> j<span class="token punctuation">]</span> <span class="token operator">=</span> isNotPrime<span class="token punctuation">;</span>
        <span class="token keyword">if</span> i <span class="token operator">%</span> j <span class="token operator">==</span> <span class="token number">0</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre></li>
<li>线性筛欧拉函数 </li>
</ul>
</li>
</ul>
<h2 id="欧拉函数"><a href="#欧拉函数" class="headerlink" title="欧拉函数"></a>欧拉函数</h2><ul>
<li>$\varphi(i)$表示小于等于i的正整数中，与i互质的数字个数</li>
<li>$\varphi(x) = x (1 - \frac{1}{p_1})(1- \frac{1}{p_2})…(1 - \frac{1}{p_n})$</li>
<li>性质<ul>
<li>$\varphi(1) = 1$ (唯一合一互质的个数是$1$本身)</li>
<li>$n$是素数，$\varphi(n) = n - 1$</li>
<li>$n$是合数，$\varphi(n) &lt; n - 1$</li>
<li>$\varphi(2 \times x) = \varphi(x)$</li>
<li>$a, b$互为质数，则$\varphi(2 \times n) = \varphi(n)$</li>
<li>$a % b = 0$ $varphi(a \times b) = \varphi(a) \times b$</li>
</ul>
</li>
<li>线性筛欧拉函数 </li>
</ul>
<h2 id="GCD"><a href="#GCD" class="headerlink" title="GCD"></a>GCD</h2><ul>
<li>BZOJ 2705 [SDOI2012]longge <ul>
<li>求$\Sigma gcd(i, N) 1 &lt;= i &lt;= N$</li>
<li>枚举gcd() = x， 统计有多少个$i$， gcd(i, N) = x</li>
<li>设出现次数为times[x]<ul>
<li>gcd(i, N) = x  ==&gt; gcd(i / x, N /x) = 1  ==&gt; $\varphi(N / x)$</li>
</ul>
</li>
<li>给一个N，把$1~N$排成一列，即</li>
</ul>
</li>
</ul>
<h2 id="费马小定理-amp-amp-欧拉定理"><a href="#费马小定理-amp-amp-欧拉定理" class="headerlink" title="费马小定理 &amp;&amp; 欧拉定理"></a>费马小定理 &amp;&amp; 欧拉定理</h2><ul>
<li><img src="./4.png" alt="4"></li>
<li><img src="./5.jpg" alt="5"><h2 id="逆元"><a href="#逆元" class="headerlink" title="逆元"></a>逆元</h2></li>
<li>$a \times b = 1 (mod p)$</li>
<li>$a^{-1}$是a的逆元<ul>
<li>费马小定理求</li>
<li>扩展欧几里得</li>
</ul>
</li>
</ul>
<h2 id="组合数"><a href="#组合数" class="headerlink" title="组合数"></a>组合数</h2><ul>
<li>$C(n, m) = n * (n-1) * (n-2) * … * (n-m+1) / m! % P$<h2 id="Lucas定理"><a href="#Lucas定理" class="headerlink" title="Lucas定理"></a>Lucas定理</h2></li>
<li><img src="./6.png" alt="6"></li>
<li>C(n, m) % p = C(n / p, m / p) * C(n % p, m % p) % p (p是素数)</li>
<li>先将P质因数分解成$P_1 P_2 P_3 P_4 P_5 ….. P_k$</li>
<li><ol>
<li>先将P分解质因数，得到k个质因子p1..pk</li>
<li><ol>
<li>对这k个质因子，用lucas定理求出C(n,m) % pi的值</li>
</ol>
</li>
<li>合并相邻的两个同余方程，要求(p1,p2) = 1  <pre><code>  4) C(n,m) = x1 (mod p1)    </code></pre>
C(n,m) = x2 (mod p2) <ol start="2">
<li>C(n,m) = p1<em>k1+x1 = p2</em>k2+x2<br>p1<em>k1 - p2</em>k2 = x2 - x1  ==&gt; exgcd  </li>
<li>用exgcd求出一组整数解(k1, k2)<br>C(n,m) = p1<em>k1+x1 + T</em>p1<em>p2是这两个同余方程的通解<br>所以C(n,m) = p1</em>k1+x1 (mod p1<em>p2)<br>C(n,m) = p1</em>k1+x1 + T<em>p1</em>p2 </li>
</ol>
</li>
<li>重复3，就可以得到C(n,m) % P的结果    </li>
</ol>
</li>
<li>P2606 [ZJOI2010]排列计数 <ul>
<li>对于一个n个元素的二叉堆，其左右儿子为根的堆，<br>大小是确定的<br>设左儿子的堆大小为l，右儿子的堆的大小为r,r=n-l-1<br>f[i]表示i个元素组成二叉堆的方案数<br>f[n] = C(n-1, l) * f[l] * f[r] % P<br>若P很大，直接做<br>若P&lt;N，1..P-1的数是有逆元的    </li>
</ul>
</li>
</ul>
<h2 id="中国剩余定理CRT"><a href="#中国剩余定理CRT" class="headerlink" title="中国剩余定理CRT"></a>中国剩余定理CRT</h2><ul>
<li><a target="_blank" rel="noopener" href="https://www.cnblogs.com/Miracevin/p/9254795.html">https://www.cnblogs.com/Miracevin/p/9254795.html</a></li>
<li><img src="./10.png" alt="10"></li>
</ul>
<h2 id="Guass消元"><a href="#Guass消元" class="headerlink" title="Guass消元"></a>Guass消元</h2><ul>
<li><p>[HNOI2013]游走<br>要求总分的期望最小 &lt;== 期望走过的次数越大的边，编号越小<br>求每条边的期望经过次数 &lt;== 每个点的期望经过次数</p>
<p>一条边 编号为k，端点为(x,y)</p>
<p>p[x]表示第x个点的期望经过次数<br>du[x]表示与x相连的点数<br>那么第k条边的期望经过次数就是 p[x] * 1/du[x] + p[y]* 1/du[y] </p>
<p>假设 x 号点与t1,t2..tk相连<br>p[1] = p[t1]/du[t1] + p[t2]/du[t2] + … + p[tk]/du[tk] + 1<br>p[x] = p[t1]/du[t1] + p[t2]/du[t2] + … + p[tk]/du[tk]<br>p[n]不会走到其他点，取消累加答案</p>
</li>
</ul>
<h2 id="大步小步定理-BSGS"><a href="#大步小步定理-BSGS" class="headerlink" title="大步小步定理(BSGS)"></a>大步小步定理(BSGS)</h2><ul>
<li><img src="./9.png" alt="9"></li>
<li><a target="_blank" rel="noopener" href="https://www.cnblogs.com/cjoieryl/p/8748022.html">https://www.cnblogs.com/cjoieryl/p/8748022.html</a></li>
</ul>
<h1 id="Day6-基础算法"><a href="#Day6-基础算法" class="headerlink" title="Day6 基础算法"></a>Day6 基础算法</h1><h2 id="Day6-T2"><a href="#Day6-T2" class="headerlink" title="Day6 T2"></a>Day6 T2</h2><ul>
<li>T2 <ul>
<li>加权并查集，特征性质并查集<ul>
<li>[L, R] % 2 == 1 ===&gt; [1, L - 1] 和 [1, R]奇偶性相反</li>
<li>[L, R] % 2 == 0 ===&gt; [1, L - 1] 和 [1, R]奇偶性相同</li>
</ul>
</li>
<li>QAQ<pre class="line-numbers language-none"><code class="language-none">        X &lt;---x--- Y                          
        ^          ^            
h[L]--&gt; |          | &lt;---  h[R]      x + h[R] &#x3D;&#x3D;&#x3D;&#x3D; h[L] + k
        L &lt;---k--- R     
             
             A
             |                      
             |                +-------------------+    
             +----------------|   平行四边形定则   |
                              +-------------------+<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

</li>
</ul>
</li>
</ul>
<h2 id="模拟"><a href="#模拟" class="headerlink" title="模拟"></a>模拟</h2><ul>
<li>对于复杂的模拟，最好的办法就是咕掉</li>
<li>代码能力<h3 id="例题-4"><a href="#例题-4" class="headerlink" title="例题"></a>例题</h3></li>
<li>时间复杂度</li>
<li>P3585 [POI2015]PIE</li>
<li>P3492 [POI2009]TAB-Arrays</li>
</ul>
<h2 id="贪心"><a href="#贪心" class="headerlink" title="贪心"></a>贪心</h2><ul>
<li>P3419 [POI2005]SAM-Toy Cars<ul>
<li>两种贪心策略<ol>
<li>把后面用到少的物品往后放</li>
<li>把后面出现晚的往后放</li>
</ol>
</li>
<li>应该现放出现晚的，相当于暂时用不到了先放到后面去。和出现次数没有什么关系</li>
</ul>
</li>
<li>CF898D Alarm</li>
<li>P3545 [POI2012]HUR-Warehouse Store</li>
<li>CF954E Water Taps</li>
<li>P3457 [POI2007]POW-The Flood</li>
</ul>
<hr>
<p>设队形为：</p>
<hr>
<ul>
<li>P3566 [POI2014] KLO-Bricks</li>
<li>P3523 [POI2011] DYN-Dynamite</li>
</ul>
<h2 id="分治"><a href="#分治" class="headerlink" title="分治"></a>分治</h2><ul>
<li>CF768B code for 1</li>
</ul>
<h1 id="Last-Day"><a href="#Last-Day" class="headerlink" title="Last Day"></a>Last Day</h1><ul>
<li>tarjan并查集 求 LCA<ul>
<li><a target="_blank" rel="noopener" href="https://www.cnblogs.com/abc2237512422/p/9832468.html">https://www.cnblogs.com/abc2237512422/p/9832468.html</a></li>
</ul>
</li>
</ul>
<h1 id="CSP-Algorithm"><a href="#CSP-Algorithm" class="headerlink" title="CSP-Algorithm"></a>CSP-Algorithm</h1><h2 id="数论"><a href="#数论" class="headerlink" title="数论"></a>数论</h2><ol>
<li>quick_power!important</li>
<li>矩阵乘法!important</li>
<li>GCD、exGCD!important</li>
<li>筛素数、素数判断、质因数分解!important</li>
<li>欧拉函数、筛欧拉函数</li>
<li>逆元</li>
<li>组合数取模/卢卡斯定理</li>
<li>中国剩余定理</li>
<li>高斯消元</li>
</ol>
<h2 id="图论"><a href="#图论" class="headerlink" title="图论"></a>图论</h2><ul>
<li><p>Tarjan</p>
</li>
<li><p>二分图</p>
</li>
<li><p>2-SAT</p>
</li>
<li><p>最小生成树</p>
</li>
<li><p>最短路</p>
<h2 id="模拟-1"><a href="#模拟-1" class="headerlink" title="模拟"></a>模拟</h2></li>
<li><p>灭鼠计划</p>
</li>
<li><p>猪国杀</p>
</li>
<li><p>立体图</p>
</li>
<li><p>操作系统</p>
</li>
<li><p>靶形数独</p>
</li>
<li><p>[THUPC2018]组合数问题</p>
<h2 id="SomeThing-3"><a href="#SomeThing-3" class="headerlink" title="SomeThing"></a>SomeThing</h2></li>
<li><p>题目中的一些奇怪的数字为突破口</p>
</li>
<li><p>数据梯度消失，增加奇怪的信息，可做<code>QAQ</code></p>
</li>
<li><p>cdqz.openjudge.cn</p>
</li>
<li><p>$O_2$实数精度过小</p>
</li>
<li><p>$O_2$局部变量不初始化</p>
</li>
<li><p>最后检查Longlong 数组大小 文件 变量初始化</p>
<h2 id="考试注意"><a href="#考试注意" class="headerlink" title="考试注意"></a>考试注意</h2></li>
<li><p>对拍</p>
<ul>
<li><p>能够找到一组使两份代码结果不同的数据，进行调试</p>
</li>
<li><p><code>random_shuffle(Begin, End)</code></p>
</li>
<li><pre><code class="cpp">//rand() Windows下面大小有限制[0, 32767] 
int _Rand()
&#123;
  return (rand() &lt;&lt; 16 ) + rand();
&#125; 
<pre class="line-numbers language-none"><code class="language-none">- 生成一棵树
  - &#96;&#96;&#96;cpp
     &#x2F;&#x2F;生成随机树，为每个节点随机父节点 
     for(int i &#x3D; 1;i &lt;&#x3D; n;i++)
       f[i] &#x3D; _Rand() % (a - 1) + 1;<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span></span></code></pre>
- ```cpp
    //生成随机树，为每个节点随机父节点 
     for(int i = 1;i &lt;= n / 2;i++)
       f[i] = i - 1;
     for(int i = 1;i &lt;= n / 2;i++)
       f[i] = _Rand() % (a - 1) + 1;</code></pre>
</li>
<li><p>DAG</p>
<ul>
<li>编号大的连向小的</li>
</ul>
</li>
</ul>
</li>
<li><p>流程</p>
<ul>
<li>10 - 15 min 读三道题<ul>
<li>题意</li>
<li>样例原理</li>
<li>题难度不一定递增</li>
</ul>
</li>
<li>5 min 决定做题顺序</li>
<li>按照决定的顺序，先写暴力<ul>
<li><code>Get</code>保底分</li>
</ul>
</li>
<li>1.5h 后 暴力代码Code结束</li>
<li>开始思考正解 （1.5h - 结束15min之前）<ul>
<li>题目中的一些奇怪的数字为突破口</li>
<li>数据梯度消失，增加奇怪的信息，可做<code>QAQ</code></li>
<li>尽可能使分数一点点递增。</li>
<li>想不到正解，提交暴力程序</li>
<li>想到正解，暴力正解对拍测试，找正解$bug$</li>
</ul>
</li>
<li>最后15分钟<ul>
<li>$O_2$实数精度过小</li>
<li>最后检查Longlong-</li>
<li>数组大小</li>
<li>文件</li>
<li>变量初始化 $O_2$局部变量不初始化</li>
</ul>
</li>
</ul>
</li>
</ul>

    </div>

    
    
    

    <footer class="post-footer">

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2019/【luogu-3026】【USACO11OPEN】学习语言Learning Languages/" rel="prev" title="【luogu-3026】【USACO11OPEN】学习语言Learning Languages">
                  <i class="fa fa-chevron-left"></i> 【luogu-3026】【USACO11OPEN】学习语言Learning Languages
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2019/「YuGu P1939」矩阵加速（数列）/" rel="next" title="「YuGu P1939」矩阵加速（数列）">
                  「YuGu P1939」矩阵加速（数列） <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
  
  
  



      
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

    </div>
  </main>

  <footer class="footer">
    <div class="footer-inner">
      

      

<div class="copyright">
  
  &copy; 2018 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">舒雨墨</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
    <span title="站点总字数">319k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:50</span>
  </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/mist/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.0/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/@next-theme/pjax@0.4.0/pjax.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>
  <script>
var pjax = new Pjax({
  selectors: [
    'head title',
    '.page-configurations',
    '.main-inner',
    '.post-toc-wrap',
    '.languages',
    '.pjax'
  ],
  analytics: false,
  cacheBust: false,
  scrollRestoration: false,
  scrollTo: !CONFIG.bookmark.enable
});

document.addEventListener('pjax:success', () => {
  pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
  NexT.boot.refresh();
  // Define Motion Sequence & Bootstrap Motion.
  if (CONFIG.motion.enable) {
    NexT.motion.integrator
      .init()
      .add(NexT.motion.middleWares.subMenu)
      .add(NexT.motion.middleWares.postList)
      .bootstrap();
  }
  const hasTOC = document.querySelector('.post-toc');
  document.querySelector('.sidebar-inner').classList.toggle('sidebar-nav-active', hasTOC);
  document.querySelector(hasTOC ? '.sidebar-nav-toc' : '.sidebar-nav-overview').click();
  NexT.utils.updateSidebarPosition();
});
</script>


  
  <script data-pjax>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>




  <script src="/js/local-search.js"></script>












  






<script data-pjax>
  (function() {
    function leancloudSelector(url) {
      return document.getElementById(url).querySelector('.leancloud-visitors-count');
    }

    function addCount(Counter) {
      const visitors = document.querySelector('.leancloud_visitors');
      const url = decodeURI(visitors.id);
      const title = visitors.dataset.flagTitle;

      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url })))
        .then(response => response.json())
        .then(({ results }) => {
          if (results.length > 0) {
            const counter = results[0];
            leancloudSelector(url).innerText = counter.time + 1;
            Counter('put', '/classes/Counter/' + counter.objectId, { time: { '__op': 'Increment', 'amount': 1 } })
              .catch(error => {
                console.error('Failed to save visitor count', error);
              });
          } else {
              Counter('post', '/classes/Counter', { title, url, time: 1 })
                .then(response => response.json())
                .then(() => {
                  leancloudSelector(url).innerText = 1;
                })
                .catch(error => {
                  console.error('Failed to create', error);
                });
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    function showTime(Counter) {
      const visitors = document.querySelectorAll('.leancloud_visitors');
      const entries = [...visitors].map(element => {
        return decodeURI(element.id);
      });
      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url: { '$in': entries } })))
        .then(response => response.json())
        .then(({ results }) => {
          for (let url of entries) {
            const target = results.find(item => item.url === url);
            leancloudSelector(url).innerText = target ? target.time : 0;
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    const { app_id, app_key, server_url } = {"enable":true,"app_id":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","app_key":"lwlhdaYvNPPDLhBEGeUegbH6","server_url":null,"security":false};
    function fetchData(api_server) {
      const Counter = (method, url, data) => {
        return fetch(`${api_server}/1.1${url}`, {
          method,
          headers: {
            'X-LC-Id'     : app_id,
            'X-LC-Key'    : app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      if (CONFIG.page.isPost) {
        if (location.hostname == '127.0.0.1' || location.hostname == 'localhost') ;
        else addCount(Counter);
      }
      if (document.querySelectorAll('.post-title-link').length >= 1 || document.querySelectorAll('.post-title').length >= 1) {
        showTime(Counter);
      }
    }

    const api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${app_id.slice(0, 8).toLowerCase()}.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(response => response.json())
        .then(({ api_server }) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>


    <div class="pjax">
  

  
      <script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              const target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    const script = document.createElement('script');
    script.src = '//cdn.jsdelivr.net/npm/mathjax@3.1.0/es5/tex-mml-chtml.js';
    script.defer = true;
    document.head.appendChild(script);
  } else {
    MathJax.startup.document.state(0);
    MathJax.typesetClear();
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  
<script>
NexT.utils.loadComments('#valine-comments', () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js', () => {
    new Valine(Object.assign({
      el  : '#valine-comments',
      path: "2019/【QBXT-20191001-20191007】MainNotice/",
    }, {"enable":true,"appId":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","appKey":"lwlhdaYvNPPDLhBEGeUegbH6","placeholder":"Just go go","avatar":"mm","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-cn","visitor":false,"comment_count":true,"recordIP":true,"serverURLs":null,"enableQQ":true,"requiredFields":[]}
    ));
  }, window.Valine);
});
</script>

    </div>
</body>
</html>
